package com.lw.leetcode.add.e;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * c
 * tree
 * 685. 冗余连接 II
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/1 11:08
 */
public class FindRedundantDirectedConnection {


    public static void main(String[] args) {
        FindRedundantDirectedConnection test = new FindRedundantDirectedConnection();

        // [[2,1]
//        int[][] arr = {{2, 1}, {3, 1}, {4, 2}, {1, 4}};

        // [[2,1]
        int[][] arr = {{1, 2}, {1, 3}, {2, 3}};

        int[] ts = test.findRedundantDirectedConnection(arr);
        System.out.println(Arrays.toString(ts));
    }

    private int n1 = 0;
    private int n2 = 0;
    private int n = 0;

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int length = edges.length;
        int[] arr = new int[length + 1];
        Map<Integer, Node> map = new HashMap<>();

        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            if (arr[b] != 0) {
                n1 = arr[b];
                n2 = a;
                n = b;
            }
            arr[b] = a;
            Node node = map.computeIfAbsent(a, v -> new Node(a));
            Node child = map.computeIfAbsent(b, v -> new Node(b));
            if (node.left == null) {
                node.left = child;
            } else {
                node.rigth = child;
            }
        }

        for (int i = length; i > 0; i--) {
            Node node = map.get(i);
            int f = find(node, 1);
            if (f != 0) {
                return check(f, map, edges);
            }
            clean(node);
        }
        return new int[]{n2, n};
    }

    private int[] check(int f, Map<Integer, Node> map, int[][] edges) {
        Set<Integer> set = new HashSet<>();
        for (Map.Entry<Integer, Node> entry : map.entrySet()) {
            Node value = entry.getValue();
            if (value.flag == f) {
                set.add(value.val);
            }
        }
        for (int i = edges.length - 1; i >= 0; i--) {
            int[] edge = edges[i];
            if (set.contains(edge[0]) && set.contains(edge[1])) {
                if (n != 0) {
                    if (edge[1] == n && (edge[0] == n1 || edge[0] == n2)) {
                        return edge;
                    }
                } else {
                    return edge;
                }
            }
        }
        return null;
    }

    private int find(Node node, int step) {
        if (node == null) {
            return 0;
        }
        int no = node.no;
        if (no != 0) {
            node.flag = no;
            return no;
        }
        node.no = step;
        int l = find(node.left, step + 1);
        if (l == 0) {
            int r = find(node.rigth, step + 1);
            node.flag = r;
            return r;
        }
        node.flag = l;
        return l;
    }

    private void clean(Node node) {
        if (node == null) {
            return;
        }
        node.no = 0;
        node.flag = 0;
        clean(node.left);
        clean(node.rigth);
    }

    private static class Node {
        private int val;
        private Node left;
        private Node rigth;
        private int no;
        private int flag;

        public Node(int val) {
            this.val = val;
        }
    }

}
